package com.hyb.algorithm.data.struct.stack;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @Author: huyanbing
 * @Date: 2021/9/3 7:41 下午
 */
public class NextGreaterElement {


    /**
     * 2 1  2  4 3
     *
     * @param args
     */
    public static void main(String[] args) {

        int[] nums = new int[]{2, 1, 2, 4, 3};

        Map<Integer,Integer> ret=new HashMap<>();

        NextGreaterElement exe = new NextGreaterElement();
        int[] temp = exe.nextGreaterElement(nums);

        for (int i = 0; i < temp.length; i++) {
            System.out.print("," + temp[i]);
        }

    }

    public int[] nextGreaterElement(int[] nums) {
        int n = nums.length;

        int[] temp = new int[n];

        Stack<Integer> stack = new Stack<>();

        //倒着入栈
        for (int i = n - 1; i >= 0; i--) {

            while (!stack.isEmpty() && stack.lastElement() <= nums[i]) {
                stack.pop();
            }

            temp[i] = stack.isEmpty() ? -1 : stack.lastElement();

            stack.push(nums[i]);
        }
        return temp;
    }


    public int[] nextGreaterElement2(int[] nums) {
        int n = nums.length;
        int[] temp = new int[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[i] >= stack.lastElement()) {
                stack.pop();
            }

            //元素身后的第一个元素
            temp[i] = stack.isEmpty() ? -1 : stack.lastElement();
            stack.push(nums[i]);

        }

        return temp;


    }
}
